There are many applications where a user needs to search for a proper name, with a limited knowledge about the name, in a database containing, for example, street names in a city or passport holders in a country. A problem may arise if the user has only a vague or uncertain knowledge about the proper spelling of the name the user is looking for (e.g., when the user has only heard the name) or if multiple spelling variants exist for the same name. This problem is worse if the user is looking for a multi-word name (e.g., a full name composed from a first name, middle names and family name) with an inaccurate knowledge about the multi-word name. For instance, the user can confuse the first name and middle names.
Given the current emergence of many solutions deployed on portable devices with limited computing resources, there is also a need for building compact dictionaries of multi-word proper names with a small memory footprint that can be searched efficiently and effectively for names where a vagueness or uncertainty exists.
The problem of vagueness or uncertainty in names is currently dealt with through wildcards to find similar names or through phonetic searches. These methods are applied to only single word names and concentrate on the search for names in documents or texts. Known search methods based on stemming techniques to reduce words to their basic forms are only useful for searching regular words and are not appropriate for searching names.
Existing methods only focusing on approximate searching for single word names in a text have numerous drawbacks including, for example:                they are not concerned with building and searching dictionaries of proper names and more specifically contracted dictionaries of proper names; and        they mainly focus on approximate searching of single word names and do not provide elaborate solutions for approximate searching of multi-word names        
U.S. Pat. No. 4,672,571 to Bass et al., entitled “Compound word suitability for spelling verification”, discloses a compound word spelling verification technique for use with a dictionary which does not include all verifiable compounds. During verification of a text word, an attempt is made to find a pair of words in the dictionary of which the text word consists. A table associated with the dictionary includes compound class information relative to each of the words stored therein. The compound class of each of the pair of words of which the input text word consists are tested for compatibility to determine if each of the pair of words may acceptably be used in a compound word in the physical position in which it is found in the input text word. U.S. Pat. No. 4,672,571 relates to compound words (which are single words) and does not disclose an approximate search method that looks for multi-word names in a dictionary that are close to a specific selected multi-word name.